polynomial-time approximation scheme

Definition

A polynomial-time approximation scheme (PTAS) is a family of algorithms $\{A_\epsilon\}$, where $\exists A_\epsilon$ for each $\epsilon > 0$, such that $A_\epsilon$ is a $(1 + \epsilon)$-approximation algorithm (for minimization problems) or a $(1 - \epsilon)$-approximation algorithm (for maximization problems).

References

1. D. P. Williamson, D. B. Shmoys. Approximation Algorithms, Cambridge University Press, 2010, p. 15.